import java.util.*;

//前K个高频单词
//测试链接 https://leetcode.cn/problems/top-k-frequent-words/
public class TopKFrequent {

    public class Pair<K, V> {
        private K key;
        private V value;
        public Pair(K key, V value) {
            this.key = key;
            this.value = value;
        }
        public K getKey() {
            return key;
        }
        public void setKey(K key) {
            this.key = key;
        }
        public V getValue() {
            return value;
        }
        public void setValue(V value) {
            this.value = value;
        }
    }

    public List<String> topKFrequent(String[] words, int k) {
        // 1. 统计⼀下每⼀个单词出现的频次
        Map<String, Integer> hash = new HashMap<>();
        for (String s : words) {
            hash.put(s, hash.getOrDefault(s, 0) + 1);
        }
        // 2. 创建⼀个⼤⼩为 k 的堆
        PriorityQueue<Pair<String, Integer>> heap = new PriorityQueue<>(
                (a, b) -> {
                    if (a.getValue().equals(b.getValue())) // 频次相同的时候，字典序按照⼤根堆的⽅式排列
                    {
                        return b.getKey().compareTo(a.getKey());
                    }
                    return a.getValue() - b.getValue();
                });
        //3.  TopK 的主逻辑

        for (

                Map.Entry<String, Integer> e : hash.entrySet()) {
            heap.offer(new Pair<>(e.getKey(), e.getValue()));
            if (heap.size() > k) {
                heap.poll();
            }
        }
        // 4. 提取结果
        List<String> ret = new ArrayList<>();
        while (!heap.isEmpty()) {
            ret.add(heap.poll().getKey());
        }
        // 逆序数组
        Collections.reverse(ret);
        return ret;
    }
}
